home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 5690 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.4 KB
  1. Path: newsfeed.gsfc.nasa.gov!usenet
  2. From: "Thomas A. McGlynn" <tam@silk.gsfc.nasa.gov>
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Tough FACTORIAL math problem...
  5. Date: Tue, 20 Feb 1996 17:23:44 -0500
  6. Organization: NASA Goddard Space Flight Center -- Greenbelt, Maryland USA
  7. Message-ID: <312A49F0.167E@silk.gsfc.nasa.gov>
  8. References: <4fr8be$ass@news.iconn.net> <31224679.6193@born.com>
  9.         <4fv74c$chq@gatekeeper.alcatel.no>
  10.         <4fvgbu$kmb@winx03.informatik.uni-wuerzburg.de> <TANMOY.96Feb15133510@qcd.lanl.gov>
  11. NNTP-Posting-Host: silk.gsfc.nasa.gov
  12. Mime-Version: 1.0
  13. Content-Type: text/plain; charset=us-ascii
  14. Content-Transfer-Encoding: 7bit
  15. X-Mailer: Mozilla 2.0 (X11; I; OSF1 V3.2 alpha)
  16.  
  17. Tanmoy Bhattacharya wrote:
  18. > 
  19. > In article <4fvgbu$kmb@winx03.informatik.uni-wuerzburg.de>
  20. > schoof@informatik.uni-wuerzburg.de (Jochen Schoof) writes:
  21. > <snip>
  22. >    I'm far from being a specialist in number theory, but as can be seen from
  23. >    my previous posting in this thread, have dealt with the problem for a while,
  24. >    too. Allow me to give some explanation why the problem can be solved by
  25. >    just keeping two digits stored. Assume we have two such digits m and n:
  26. > 
  27. >      x = 10 * m + n;  with  0<=m<=9 and 1<=n<=9
  28. > 
  29. >    When multiplying to another number y the LSD of the result can be determined
  30. >    by calculating LSD(n*LSD(y)) in most cases (see tabular below).
  31. ....
  32. If you think about this long enough, it becomes clear that the last digit
  33. then must be cyclic with a period of no longer than 40.  Consider pairs of
  34. last digits of numbers and their factorials.  The last digit of the factorial
  35. must be one of 2,4,6,8 (for n>1) so the combination of the last digit of
  36. n and the last digit of n! must repeat within a cycle of 40 iterations.
  37. But since the sequence of last digits of n is fixed (ie., 1234567890), and
  38. we're starting with the same last digit of n!, the last digits of n! must
  39. repeat.  Thus the function should be writeable in terms of a lookup table
  40.  
  41. i.e. you should be able to code it something like:
  42.  
  43.     if (n > CYCLE_START)
  44.          last_digit = cycle[ (n-CYCLE_START)%CYCLE_LENGTH];
  45.     else if (n>=0) 
  46.          last_digit = first_cycle[n];
  47.  
  48. where the values of cycle and first_cycle need to be determined once and
  49. for all.  We know that CYCLE_START <= 41 and CYCLE_LENGTH <= 40.
  50.  
  51. No doubt someone else has presented this solution as well.  This problem
  52. has generated an impressive amount of traffic....
  53.  
  54.         Tom McGlynn
  55.             Goddard Space Flight Center
  56.